import java.util.HashSet;
import java.util.Set;

/**
 * 1733. 需要教语言的最少人数
 * https://leetcode-cn.com/problems/minimum-number-of-people-to-teach/
 * 只能选择一门语言，来尽可能少的教会部分用户，达到 friendsships 中的朋友关系都成立的效果
 */
public class Solutions_1733 {
    public static void main(String[] args) {
//        int n = 2;
//        int[][] languages = {{1}, {2}, {1, 2}};
//        int[][] friendships = {{1, 2}, {1, 3}, {2, 3}};  // output: 1
        // 解释：你可以选择教用户 1 第二门语言，也可以选择教用户 2 第一门语言。

//        int n = 17;
//        int[][] languages = {{4, 7, 2, 14, 6}, {15, 13, 6, 3, 2, 7, 10, 8, 12, 4, 9}, {16}, {10}, {10, 3}, {4, 12, 8, 1, 16, 5, 15, 17, 13}, {4, 13, 15, 8, 17, 3, 6, 14, 5, 10}, {11, 4, 13, 8, 3, 14, 5, 7, 15, 6, 9, 17, 2, 16, 12}, {4, 14, 6}, {16, 17, 9, 3, 11, 14, 10, 12, 1, 8, 13, 4, 5, 6}, {14}, {7, 14}, {17, 15, 10, 3, 2, 12, 16, 14, 1, 7, 9, 6, 4}};
//        int[][] friendships = {{4, 11}, {3, 5}, {7, 10}, {10, 12}, {5, 7}, {4, 5}, {3, 8}, {1, 5}, {1, 6}, {7, 8}, {4, 12}, {2, 4}, {8, 9}, {3, 10}, {4, 7}, {5, 12}, {4, 9}, {1, 4}, {2, 8}, {1, 2}, {3, 4}, {5, 10}, {2, 7}, {1, 7}, {1, 8}, {8, 10}, {1, 9}, {1, 10}, {6, 7}, {3, 7}, {8, 12}, {7, 9}, {9, 11}, {2, 5}, {2, 3}};
        // output: 4

        int n = 3;
        int[][] languages = {{2}, {1, 3}, {1, 2}, {3}};
        int[][] friendships = {{1, 4}, {1, 2}, {3, 4}, {2, 3}};  // output: 2
        // 解释：教用户 1 和用户 3 第三门语言，需要教 2 名用户。

        int result = minimumTeachings(n, languages, friendships);
        System.out.println(result);
    }

    /**
     * 解题思路：
     * 若 A、B、C、D 四人无法沟通，假设教四人都学习语言 1，那么结果为 4
     * 可是，题目要求返回 最少 需要教会多少名用户
     * 采用贪心思想
     * 假如 A、B 都掌握了语言 2，那么我们也教 C、D 语言 2，此时，教会 2 人即可
     * 假如 A、B、C 都掌握了语言 3，那么我们也教 D 语言 3，此时，教会 1 人即可
     *
     * 中心思想：n 种语言中，要想教的人尽可能得少，就得在无法沟通的人当中找出哪种语言被掌握得最多
     */
    public static int minimumTeachings(int n, int[][] languages, int[][] friendships) {
        int userCnt = languages.length;
        // matrix[1][2] = true，表示用户 1 掌握了语言 2
        boolean[][] matrix = new boolean[userCnt + 1][n + 1];

        for (int i = 0; i < languages.length; i++) {
            for (int j = 0; j < languages[i].length; j++) {
                int userIdx = i + 1;
                int languageIdx = languages[i][j];
                matrix[userIdx][languageIdx] = true;
            }
        }

        // 记录下无法沟通而又需要成为好友的人
        Set<Integer> set = new HashSet<>();

        for (int[] friendship : friendships) {
            int user1 = friendship[0], user2 = friendship[1];
            boolean flag = false;

            // 遍历全部的语言，判断两人是否都掌握了某种语言
            for (int i = 1; i <= n; i++) {
                if (matrix[user1][i] && matrix[user2][i]) {
                    flag = true;
                    break;
                }
            }
            if (flag) {
                continue;
            }
            set.add(user1);
            set.add(user2);
        }

        int res = 0;
        // teachCnt[1] = 2，表示语言 1 已经有 2 人掌握
        int[] teachCnt = new int[n + 1];

        for (int user : set) {
            for (int i = 1; i <= n; i++) {
                if (matrix[user][i]) {
                    teachCnt[i] ++;
                    res = Math.max(res, teachCnt[i]);
                }
            }
        }
        return set.size() - res;
    }
}
